package jjn.round1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jiang Jining
 * @since 2023-06-11 10:27
 */
public class LeetCode131_PalindromePartitioning {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(String s, int startIndex, List<String> path, List<List<String>> result) {
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                String substring = s.substring(startIndex, i + 1);
                path.add(substring);
            } else {
                continue;
            }
            backtrack(s, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean isPalindrome(String s, int starIndex, int endIndex) {
        int left = starIndex, right = endIndex;
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}
